package 程序员面试金典;

/**
 * 面试题 02.04. 分割链表
 * 给你一个链表的头节点 head 和一个特定值 x ，请你对链表进行分隔，使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。
 *
 * 你不需要 保留 每个分区中各节点的初始相对位置。
 *
 *
 *
 * 示例 1：
 *
 *
 * 输入：head = [1,4,3,2,5,2], x = 3
 * 输出：[1,2,2,4,3,5]
 * 示例 2：
 *
 * 输入：head = [2,1], x = 2
 * 输出：[1,2]
 *
 *
 * 提示：
 *
 * 链表中节点的数目在范围 [0, 200] 内
 * -100 <= Node.val <= 100
 * -200 <= x <= 200
 */
public class T02_04 {
    public ListNode partition(ListNode head, int x) {


        ListNode listNode = new ListNode(-201);
        listNode.next = head;
        ListNode curr = new ListNode(-202);
        curr.next = head;
//首先找到第一个大于等于x 所在的节点
        while (listNode.next != null) {
            if (listNode.next.val >= x) {
                break;
            } else {
                listNode = listNode.next;
            }
        }


        while (listNode != null && listNode.next != null) {
            if (listNode.next.val < x) { //将此节点移动到 头部

                ListNode temp = listNode.next; //保存要移动的节点
                listNode.next = listNode.next.next; //删除此节点
                //在前面插入
                temp.next = curr.next;
                curr.next = temp;

            } else {
                listNode = listNode.next;
            }


        }


        return curr.next;


    }

    /**
     * 链表的定义
     */
    static class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
        }
    }

    public static void main(String[] args) {
        //[1,4,3,2,5,2]
        T02_04 t02_04 = new T02_04();
        ListNode listNode = new ListNode(1);
        ListNode listNode3 = new ListNode(3);
        ListNode listNode2 = new ListNode(2);


        listNode.next = listNode2;
        listNode3.next = listNode;

        ListNode partition = t02_04.partition(listNode3, 3);
    }
}
